#include <bits/stdc++.h>
using namespace std;

// 【题目】力扣1186. 删除一次得到子数组最大和
// 【难度】中等
// 【提交】2025.10.09 https://leetcode.cn/problems/maximum-subarray-sum-with-one-deletion/submissions/669105824/
// 【标签】动态规划；数组
class Solution_LC1186 {
public:
    int maximumSum(vector<int>& arr) {
        int res = arr[0], dp0 = arr[0], dp1 = 0;
        for(int i = 1; i < arr.size(); i++) {
            dp1 = max(dp0, dp1 + arr[i]);
            dp0 = max(dp0, 0) + arr[i];
            res = max(res, max(dp0, dp1));
        }
        return res;
    }
};

/**
 * @brief 学习总结：
 * 一、题意与模型
 * 给定一个整数数组arr，可以从中删除一个元素（也可以不删除），
 * 返回删除后（或未删除）的非空子数组的最大和。
 * 模型：动态规划，使用两个状态分别表示未删除和已删除的情况。
 * 
 * 二、标准解法状态设计
 * 1. dp0: 以当前元素结尾且未删除任何元素的子数组最大和。
 * 2. dp1: 以当前元素结尾且已删除一个元素的子数组最大和。
 * 3. res: 记录全局最大和。
 * 
 * 三、你的实现思路
 * 使用双状态动态规划，在一次遍历中同时维护未删除和已删除两种情况的最大和。
 * 通过比较两种情况的结果，得到最终答案。
 * 
 * 四、逐行注释（带细节提醒）
 * int res = arr[0], dp0 = arr[0], dp1 = 0; // 初始化变量
 * 
 * for(int i = 1; i < arr.size(); i++) { // 遍历数组
 *     dp1 = max(dp0, dp1 + arr[i]); // 更新已删除状态：
 *                                   // - 删除当前元素：继承dp0（上一状态未删除）
 *                                   // - 不删除当前元素：dp1 + arr[i]（之前已删除过）
 *     dp0 = max(dp0, 0) + arr[i];   // 更新未删除状态：标准Kadane算法
 *     res = max(res, max(dp0, dp1)); // 更新全局最大和
 * }
 * return res; // 返回结果
 * 
 * 五、正确性证明
 * 动态规划状态转移的正确性：
 * 1. dp0: 标准的最大子数组和问题，使用Kadane算法。
 * 2. dp1: 有两种选择：
 *    - 删除当前元素：那么当前状态等于dp0（上一状态未删除的最大和）
 *    - 不删除当前元素：那么当前状态等于dp1 + arr[i]（之前已经删除过一个元素）
 * 3. 通过比较dp0和dp1，可以确保找到删除0次或1次的最大子数组和。
 * 
 * 六、复杂度
 * 时间：O(n)，只需遍历数组一次。
 * 空间：O(1)，只使用了常数级别的额外空间。
 * 
 * 七、优缺点分析
 * 优点：
 *   - 时间复杂度低，只需一次遍历；
 *   - 空间复杂度低，无需额外数组；
 *   - 算法巧妙，同时处理删除和不删除两种情况。
 * 缺点：
 *   - 动态规划状态转移理解起来有一定难度；
 *   - 无法直接获取具体删除的是哪个元素。
 * 
 * 八、改进建议
 * 1. 可以添加输入验证：if (arr.empty()) return 0;
 * 2. 使用更明确的变量名（如 noDelete 代替 dp0，oneDelete 代替 dp1）来增强可读性；
 * 3. 对于教学场景，可以添加注释解释状态转移的两种选择。
 * 
 * 九、一句话总结
 * 通过双状态动态规划，你的实现巧妙地解决了"删除一次得到子数组最大和"问题，
 * 展现了动态规划在处理复杂约束条件时的应用能力。
 */